{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Calc without Closures\n",
    "\n",
    "Consider the final version of Calc, as given in Exam #2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define list-of\n",
    "  (lambda (f)\n",
    "    (lambda (ls)\n",
    "      (let loop ((ls ls))\n",
    "        (cond\n",
    "         ((null? ls) #t)\n",
    "         ((f (car ls)) (loop (cdr ls)))\n",
    "         (else #f))))))\n",
    "\n",
    "(define procedure-or-var?\n",
    "  (lambda (exp)\n",
    "    (or (var-exp? exp)\n",
    "        (procedure-exp? exp))))\n",
    "\n",
    "(define var-exp?\n",
    "  (lambda (exp)\n",
    "    (eq? (car exp) 'var-exp)))\n",
    "\n",
    "(define procedure-exp?\n",
    "  (lambda (exp)\n",
    "    (eq? (car exp) 'procedure-exp)))\n",
    "\n",
    "(define closure-exp?\n",
    "  (lambda (exp)\n",
    "    (eq? (car exp) 'closure-exp)))\n",
    "\n",
    "(define operator?\n",
    "  (lambda (item)\n",
    "    (member item '(+ - * /))))\n",
    "\n",
    "(define true?\n",
    "  (lambda (v)\n",
    "    (and (number? v)\n",
    "         (not (= v 0)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define closure-exp->body\n",
    "  (lambda (closure)\n",
    "    (cadddr closure)))\n",
    "\n",
    "(define closure-exp->parameters\n",
    "  (lambda (closure)\n",
    "    (caddr closure)))\n",
    "\n",
    "(define closure-exp->env\n",
    "  (lambda (closure)\n",
    "    (cadr closure)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define-datatype\n",
    " calc-exp calc-exp?\n",
    " (lit-exp \n",
    "  (value number?))\n",
    " (var-exp \n",
    "  (name symbol?))\n",
    " (if-exp\n",
    "  (test-exp calc-exp?)\n",
    "  (then-exp calc-exp?)\n",
    "  (else-exp calc-exp?))\n",
    " (procedure-exp\n",
    "  (parameters (list-of symbol?))\n",
    "  (body calc-exp?))\n",
    " (closure-exp\n",
    "  (env list?)\n",
    "  (parameters (list-of symbol?))\n",
    "  (body calc-exp?))\n",
    " (let-exp\n",
    "  (variables (list-of symbol?))\n",
    "  (values (list-of calc-exp?))\n",
    "  (body calc-exp?))\n",
    " (assignment-exp\n",
    "  (variable symbol?)\n",
    "  (value calc-exp?))\n",
    " (define-exp\n",
    "  (variable symbol?)\n",
    "  (value calc-exp?))\n",
    " (app-exp\n",
    "  (procedure procedure-or-var?)\n",
    "  (args (list-of calc-exp?))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define parser\n",
    "  (lambda (exp)\n",
    "    (cond\n",
    "     ((symbol? exp) (var-exp exp)) ;; apple\n",
    "     ((number? exp) (lit-exp exp)) ;; 1.2\n",
    "     ((eq? (car exp) 'lambda) ;; (lambda (a b c) a)\n",
    "      (procedure-exp \n",
    "       (cadr exp) (parser (caddr exp))))\n",
    "     ((eq? (car exp) 'let) ;; (let ((x 1)) x)\n",
    "      (let-exp \n",
    "       (map car (cadr exp))\n",
    "       (map parser (map cadr (cadr exp)))\n",
    "       (parser (caddr exp))))\n",
    "     ((eq? (car exp) 'if)   ;; (if test then else)\n",
    "      (if-exp (parser (cadr exp)) \n",
    "              (parser (caddr exp))\n",
    "              (parser (cadddr exp))))\n",
    "     ((eq? (car exp) 'set!) ;; (set! x 1)\n",
    "      (assignment-exp\n",
    "       (cadr exp)\n",
    "       (parser (caddr exp))))\n",
    "     ((and (= (length exp) 3) (operator? (cadr exp))) ;; infix\n",
    "      (app-exp (parser (cadr exp))\n",
    "               (list (parser (car exp))\n",
    "                     (parser (caddr exp)))))\n",
    "     ((eq? (car exp) 'define)      ;; (define x 1)\n",
    "      (define-exp (cadr exp) (parser (caddr exp))))\n",
    "     (else (app-exp (parser (car exp))   ;; (+ 3 4)\n",
    "                    (map parser (cdr exp)))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(import \"math\")\n",
    "(define toplevel-env \n",
    "  (list (list (list 'pi math.pi)\n",
    "              (list 'e  math.e)\n",
    "              (list '+ +)\n",
    "              (list '- -)\n",
    "              (list '* *)\n",
    "              (list '/ /)\n",
    "              (list 'list list)\n",
    "              (list '= (lambda (a b) \n",
    "                             (if (and (number? a)\n",
    "                                      (number? b)\n",
    "                                      (= a b))\n",
    "                                  1 0)))\n",
    "              (list '< (lambda (a b) (if (< a b) 1 0)))\n",
    "              (list '> (lambda (a b) (if (> a b) 1 0)))\n",
    "              )))\n",
    "\n",
    "(define extend-env!\n",
    "    (lambda (vars vals env)\n",
    "      (cond\n",
    "       ((null? vars) env)\n",
    "       (else \n",
    "        (begin\n",
    "         (set-car! env (cons (list (car vars)\n",
    "                                   (car vals))\n",
    "                             (car env)))\n",
    "         (extend-env! (cdr vars) (cdr vals) env))))))\n",
    "  \n",
    "(define extend-env\n",
    "    (lambda (vars vals env)\n",
    "      (cons (map (lambda items items) vars vals) env)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define lookup-binding\n",
    "  (lambda (name env search-first-only)\n",
    "    (cond\n",
    "     ((null? env) #f)\n",
    "     (else (let ((frame (car env)))\n",
    "             (let ((binding (assq name frame)))\n",
    "               (if binding\n",
    "                   binding\n",
    "                   (if search-first-only\n",
    "                       #f\n",
    "                       (lookup-binding name (cdr env) #f)))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define evaluator\n",
    "  (lambda (ast env) \n",
    "    (record-case ast\n",
    "      (lit-exp (value) value)\n",
    "      (var-exp (name) (let ((binding (lookup-binding name env #f)))\n",
    "                        (if binding\n",
    "                            (cadr binding)\n",
    "                            (error 'evaluator \"no such variable: ~a\" name))))\n",
    "      (procedure-exp (parameters body)\n",
    "         (closure-exp env parameters body))\n",
    "      (if-exp (test-exp then-exp else-exp)\n",
    "        (if (true? (evaluator test-exp env))\n",
    "            (evaluator then-exp env)\n",
    "            (evaluator else-exp env)))\n",
    "      (let-exp (variables values body)\n",
    "        (evaluator body\n",
    "                   (cons (map list variables (map (lambda (e) (evaluator e env)) values))\n",
    "                         env)))\n",
    "      (assignment-exp (variable value)\n",
    "        (begin \n",
    "         (set-car! (cdr (lookup-binding variable env #f)) \n",
    "                   (evaluator value env))\n",
    "         (cadr (lookup-binding variable env #f))))\n",
    "      (define-exp (variable value)\n",
    "        (let ((binding (lookup-binding variable env #t))\n",
    "              (v (evaluator value env)))\n",
    "          (if binding\n",
    "              (set-car! (cdr binding) v)\n",
    "              (begin \n",
    "               (extend-env! (list variable) \n",
    "                            (list v)\n",
    "                            env)\n",
    "               (void)))))\n",
    "      (app-exp (procedure args)\n",
    "        (applier (evaluator procedure env) \n",
    "                 (map (lambda (e) (evaluator e env)) args) \n",
    "                      env)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define applier\n",
    "  (lambda (f values env)\n",
    "    (cond\n",
    "     ((closure-exp? f) \n",
    "      (evaluator (closure-exp->body f) \n",
    "                 (extend-env (closure-exp->parameters f) \n",
    "                             values (closure-exp->env f))))\n",
    "     (else (apply f values)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define calc\n",
    "  (lambda (exp)\n",
    "      (evaluator (parser exp) toplevel-env)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(calc '(define f (let ((x 42)) (lambda () x))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(calc '(f))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(calc '(define x 100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(calc '(f))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take a look at where a closure is applied:\n",
    "\n",
    "```scheme\n",
    "(define applier\n",
    "  (lambda (f values env)\n",
    "    (cond\n",
    "     ((closure-exp? f) \n",
    "      (evaluator (closure-exp->body f) \n",
    "                 (extend-env (closure-exp->parameters f) \n",
    "                             values (closure-exp->env f))))\n",
    "     (else (apply f values)))))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define applier\n",
    "  (lambda (f values env)\n",
    "    (cond\n",
    "     ((closure-exp? f) \n",
    "      (evaluator (closure-exp->body f) \n",
    "                 (extend-env (closure-exp->parameters f) \n",
    "                             values env)))\n",
    "     (else (apply f values)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(calc '(define f (let ((x 42)) (lambda () x))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(calc '(f))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `x` in the `let` is still a `local variable`, its just that it only exists dynamically, not statically.\n",
    "\n",
    "`lexical` or `static scope`: used with closures; variables statically bound at compile/parse time (\"early binding\")\n",
    "\n",
    "`dynamic scope`: variables dynamically bound at lookup/runtime (\"late binding\")\n",
    "\n",
    "https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scope_vs._dynamic_scope\n",
    "\n",
    "This means that lexically-bound variables don't need a lookup at all at runtime... variables could be directly connected to the association that they are bound with.\n",
    "\n",
    "`lexical address` - instead of just marking a variable as a `var-exp` when parsed, it could be replaced with an address (in environment) of the value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(app-aexp (lambda-aexp (x) ((lexical-address-aexp 0 0 x none)) none) ((lit-aexp 1 none)) none)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(parse '(let ((x 1)) x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(app-aexp (lambda-aexp (x y) ((lexical-address-aexp 0 1 y none)) none) ((lit-aexp 1 none) (lit-aexp 2 none)) none)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(parse '(let ((x 1) (y 2)) y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(use-lexical-address)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(use-lexical-address #f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(app-aexp (lambda-aexp (x) ((var-aexp x none)) none) ((lit-aexp 1 none)) none)"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(parse '(let ((x 1)) x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(app-aexp (lambda-aexp (x y) ((var-aexp y none)) none) ((lit-aexp 1 none) (lit-aexp 2 none)) none)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(parse '(let ((x 1) (y 2)) y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto Scheme 2",
   "language": "scheme",
   "name": "calysto_scheme"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "scheme"
   },
   "mimetype": "text/x-scheme",
   "name": "scheme",
   "pygments_lexer": "scheme"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}